import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2024-04-18
 * Time: 22:00
 */
//1218.最长定差子序列
//这题不能沿用之前的方法,需要优化,放在hash查找很快时间复杂度低
class Solution5 {
    public int longestSubsequence(int[] arr, int difference) {
        //进行优化 hash 存 arr[i] dp[i]
        int n = arr.length;
        Map<Integer,Integer> hash = new HashMap<>();
        int ret = 1;
        for(int x : arr) {
            hash.put(x,hash.getOrDefault(x-difference,0)+1);
            ret = Math.max(ret,hash.get(x));
        }
        return ret;
    }
}
